1. Field of the Invention
The present invention relates to a search method for problem-solving in an artificial intelligence computer system, more precisely, a searching method which is useful, for example, in finding a correct word or sentence from a candidate lattice of characters or words, in a character recognition system or a speech recognition system.
2. Description of the Related Art
In a character recognition system, data of a word comprising several characters are input from an input tablet. The system compares input patterns extracted from the data with prepared standard patterns relating to individual characters, and outputs several candidates of characters and their match scores which are a measure of similarity of the candidate to the input character. A candidate lattice is constructed from the candidates each having match scores, and the candidate lattice is searched according to a predetermined procedure.
Whether the current candidate is correct is decided by collating with a word dictionary, by checking the grammar, or by a user checking the displayed word or sentence.
Usually, a depth first search is employed as the search procedure of the candidate lattice. Generally, the depth first search requires numerous searching steps to attain the correct candidate in this type of candidate lattice.
A best first search which is a kind of a breadth first search, wherein a more likely candidate, i.e., a candidate having a smaller match score is searched prior to others, is known. The conventional best first search, however, sometimes requires excessive searching steps, because only the absolute values of the match scores are considered, but the relationship with a next likely candidate is not considered.